package com.yun.datastructure.map.hashmap;

public class MyHashMap<K, V> {
    static class Entry<K, V> {
        //final可以保证key值无法被改变,确保键的不可变性,从而保证哈希表的一致性.
        final K key;
        V value;
        Entry<K, V> next;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private static final int DEFAULT_CAPACITY = 16;

    private static final double LOAD_FACTOR = 0.75;

    private Entry<K, V>[] table;

    private int size;

    private int threshold;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        table = (Entry<K, V>[]) new Entry[DEFAULT_CAPACITY];
        size = 0;
        threshold = (int) (DEFAULT_CAPACITY * LOAD_FACTOR);
    }

    //put,get,扩容
    public void put(K key, V value) {
        int hash = hash(key);
        int index = hash & (table.length - 1);
        if (table[index] == null) {
            table[index] = new Entry<>(key, value);
        } else {
            Entry<K, V> entry = table[index];
            while (entry != null) {
                if (key.equals(entry.key)) {
                    entry.value = value;
                    return;
                }
                if (entry.next == null) {
                    entry.next = new Entry<>(key, value);
                    break;
                }
                entry = entry.next;
            }
        }
        size++;
        if (size > threshold) {
            resize();
        }
    }

    public V get(K key) {
        int hash = hash(key);
        int index = hash & (table.length - 1);
        if (table[index] == null) {
            return null;
        } else {
            Entry<K, V> entry = table[index];
            while (entry != null) {
                if (key.equals(entry.key)) {
                    return entry.value;
                }
                entry = entry.next;
            }
        }
        return null;
    }

    private void resize() {
        @SuppressWarnings("unchecked")
        Entry<K, V>[] newTable = (Entry<K, V>[]) new Entry[table.length << 1];
        for (int i = 0; i < table.length; i++) {
            Entry<K, V> p = table[i];
            if (p != null) {
                Entry<K, V> aHead = null;
                Entry<K, V> bHead = null;
                Entry<K, V> a = null;
                Entry<K, V> b = null;
                while (p != null) {
                    if ((p.key.hashCode() & table.length) == 0) {
                        if (a != null) {
                            a.next = p;
                        } else {
                            aHead = p;
                        }
                        a = p;
                    } else {
                        if (b != null) {
                            b.next = p;
                        } else {
                            bHead = p;
                        }
                        b = p;
                    }
                    p = p.next;
                }
                if (a != null) {
                    a.next = null;
                    newTable[i] = aHead;
                }
                if (b != null) {
                    b.next = null;
                    newTable[i + table.length] = bHead;
                }
            }
        }
        table = newTable;
        threshold = (int)(LOAD_FACTOR * table.length);
    }

    private int hash(K key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
}
